Szpilrajn extension theorem

In mathematics, the Szpilrajn extension theorem, due to Edward Szpilrajn (1930) (later called Edward Marczewski), is one of many examples of the use of the axiom of choice (in the form of Zorn's lemma) to find a maximal of a set with certain given properties.

The theorem states that, given a binary relation R that is irreflexive and transitive it is always possible to find an extension of the relation (i.e. a relation T that strictly includes R) which is asymmetric, negatively transitive and connected.

First of all, we need some definitions to be clear upon the terminology we will use speaking about relations with particular properties.

1 Definition (negative transitivity)
2 Definition (connection)
3 Properties
4 Definition (strict orders)
5 Lemma
6 Theorem (Szpilrajn's extension theorem)
7 Proof
8 References

Definition (negative transitivity)

Given a binary relation $R \subseteq X\times X$ on a generic set $X$ , we say that $R$ is negatively transitive if

$\forall \ x,y,z\in X \ \ \neg (xRz) \and \neg (zRy) \Rightarrow \neg (xRy),$

where by $\neg(xRy)$ we mean $(x,y)\not \in R.$

Note that negative transitivity can also be rewritten as : $\forall \ x,y,z\in X \ \ (xRy) \Rightarrow (xRz) \or (zRy)$ , simply using the fact that $A \Rightarrow B$ can be rewritten as $\neg A \or B$

Definition (connection)

Given a binary relation $R \subseteq X\times X$ on a generic set $X$ , we say that R is connected (weakly) if : $\forall x,y \in X�: x\not = y$ either $x R y$ or $y R x$ .

We say that R is strictly connected or complete if $\forall x,y \in X, xRy \or yRx$ .

Properties

This properties on binary relations can be easily checked by definition:

R is irreflexive and transitive $\Rightarrow$ R is asymmetric.

R is asymmetric, transitive and connected $\Rightarrow$ R is negatively transitive.

To enounce precisely the theorem, we need yet a couple of definitions and a useful, simple lemma.

Definition (strict orders)

We say that a binary relation R is a strict partial order if it is irreflexive and transitive.

We say that a binary relation R is a strict order if it is asymmetric, negatively transitive and complete.

Lemma

Let R be a strict partial order on X. Then there exists another binary relation T on X which is still a strict partial order and extends R, hence:

$\exists T \subseteq X\times X$ such that $R\subset T$ and T is another strict partial order on X.

This lemma can be easily proved, by taking $x\not =y \in X$ such that $\neg(xRy) \and \neg(yRx)$ , which exists since the relation is not connected.

Naming:

$Rx=\{z \in X | zRx\}$

$yR=\{z \in X | yRz\}$

we can define another relation:

$S=\{x\}\cup Rx \times \{y\}\cup yR \subseteq X \times X.$

Finally, set $T=R \cup S$ which is trivially an extension of R and another strict partial order on X.

Theorem (Szpilrajn's extension theorem)

Let R be a strict partial order on a set X. Then there exists a relation T that extends R and is a strict order on X.

Proof

Let $\mathcal{P}=\{P: R\subset P$ , P is a strict partial order on X $\}$ .

We want to show the existence of a maximal element in $\mathcal{P}$ with respect to set inclusion.

To do this, we will use Zorn's Lemma. First of all we want to verify the hypothesis of the Lemma, hence that any chain (respect to inclusion) of $\mathcal{P}$ admits an upper bound in $\mathcal{P}$ .

Let $\mathcal{C}$ be a chain in $\mathcal{P}$ .

Define

$\mathcal{M}=\bigcup_{C\in \mathcal{C}} C.$

Clearly $\mathcal{M}$ is an upper bound to the chain, but we have to show that $\mathcal{M}\in \mathcal{P}$ , hence that $\mathcal{M}$ is another strict partial order which extends R.

Obviously it contains R, as all $C\in \mathcal{C}$ contains R, and it is irreflexive, as $(\bigcup_{C\in \mathcal{C}} C)\cap \Delta_{X} = \bigcup_{C\in \mathcal{C}} (C \cap\Delta_{X})=\empty$ , since any

$C\in \mathcal{C}$ is irreflexive,

$\Delta_{X}=\{(x,x)|x \in X\}.$

We have to show that $\mathcal{M}$ is transitive and here we use the chain properties of $\mathcal{C}$ .

Let $x,y,z \in X$ such that $x\mathcal{M}y \and y\mathcal{M}z$ iff $(x,y),(y,z) \in \mathcal{M}$ .

As $\mathcal{M}$ is defined as a union of sets, there exists

$P_1,P_2\in \mathcal{C}$ such that $(x,y)\in P_1, (y,z)\in P_2.$ .

But $\mathcal{C}$ is a chain with respect to inclusion, hence it holds that $P_1 \subseteq P_2$ or viceversa, so that the two couples of elements of X both belong to the same set in the union, and that set is a transitive relation; then also $(x,z)$ is in that set, hence in $\mathcal{M}$ .

Applying Zorn's Lemma, we deduce that $\mathcal{P}$ admits an upper bound with respect to set inclusion; let's call T that bound.

T has to be a complete relation, as if it was not, we could construct (exactly as in the preceding Lemma) another binary relation which strictly extends (strictly includes) T and is a strict partial order, so yet another element of $\mathcal{P}$ , contradicting that T is a maximal of $\mathcal{P}$ .

So T is an irreflexive, transitive and complete binary relation on X. But as we observed above, irreflexivity and transitivity give asymmetry that, with transitivity and completeness, give negative transitivity.

Hence T is a strict order on X that extends the partial order R.

References

Szpilrajn, E. (1930), "Sur l'extension de l'ordre partiel", Fundamenta Mathematicae 16: 386–389, ISSN 0016-2736, http://matwbn.icm.edu.pl/tresc.php?wyd=1&tom=16